package algorithms.search;

/**
 * 拉链法实现的散列表
 * @author glogo
 *
 * @param <Key>
 * @param <Value>
 */
public class SeparateChainingHashST<Key, Value> {

	private static final int INIT_CAPACITY = 4;
	
	private int N;	//键值对的数量
	private int M;	//哈希表的长度
	private SequentialSearchST<Key, Value>[] st;
	
	/**
	 * 默认构造函数
	 */
	public SeparateChainingHashST() {
		this(INIT_CAPACITY);
	}
	
	public SeparateChainingHashST(int capacity) {
		this.M = capacity;
		this.st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
		for(int i = 0; i < M; i++)
			st[i] = new SequentialSearchST<Key, Value>();
	}
	
	//返回key的hash值，在0～M-1之间
	private int hash(Key key){
		return (key.hashCode() & 0x7fffffff) % M;
	}
	
	public int size(){
		return N;
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
	
	public boolean contains(Key key){
		return get(key) != null;
	}
	
	public Value get(Key key){
		int hash = hash(key);
		return st[hash].get(key);
	}
	
	public void put(Key key, Value value){
		if (value == null) { delete(key); return; }

        // double table size if average length of list >= 10
        if (N >= 10*M) resize(2*M);
		st[hash(key)].put(key, value);
	}
	
	public void delete(Key key){
		int i = hash(key);
		if(st[i].contains(key)){
			st[i].delete(key); 	N--;
		}
		// halve table size if average length of list <= 2
        if (M > INIT_CAPACITY && N <= 2*M) resize(M/2);
	}

	// resize the hash table to have the given number of chains b rehashing all of the keys
    private void resize(int chains) {
        SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains);
        for (int i = 0; i < M; i++) {
            for (Key key : st[i].keys()) {
                temp.put(key, st[i].get(key));
            }
        }
        this.M  = temp.M;
        this.N  = temp.N;
        this.st = temp.st;
    }
	
 // return keys in symbol table as an Iterable
    public Iterable<Key> keys() {
        Queue<Key> queue = new Queue<Key>();
        for (int i = 0; i < M; i++) {
            for (Key key : st[i].keys())
                queue.enqueue(key);
        }
        return queue;
    } 
}
